//给你一个非负整数数组 nums 和一个整数 target 。 
//
// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： 
//
// 
// 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 
// 
//
// 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,1,1,1], target = 3
//输出：5
//解释：一共有 5 种方法让最终目标和为 3 。
//-1 + 1 + 1 + 1 + 1 = 3
//+1 - 1 + 1 + 1 + 1 = 3
//+1 + 1 - 1 + 1 + 1 = 3
//+1 + 1 + 1 - 1 + 1 = 3
//+1 + 1 + 1 + 1 - 1 = 3
// 
//
// 示例 2： 
//
// 
//输入：nums = [1], target = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 20 
// 0 <= nums[i] <= 1000 
// 0 <= sum(nums[i]) <= 1000 
// -1000 <= target <= 1000 
// 
//
// Related Topics 数组 动态规划 回溯 👍 2116 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-04-01 23:54:40
 * @description 494.目标和
 */
public class TargetSum{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 TargetSum fun=new TargetSum();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //1.位运算最长20位，可以每一个位置的01状态，判断结果 时间复杂度k n
	     //2.dfs回溯
		 int res=0;
	public int findTargetSumWays1(int[] nums, int target) {
		dfs(nums,0,0,target);
		return res;
	}
	private void dfs(int [] nums,int sum,int ind,int k){
		if(ind==nums.length){
			if(sum==k)
				res++;
			return;
		}
		dfs(nums,sum+nums[ind],ind+1,k);
		dfs(nums,sum-nums[ind],ind+1,k);
	}
	/*
    * 按照题意，其实就是准备两个背包，一个背包package_a存放标记为正的元素，
    * 另一个背包package_b存放标记为负的元素。package_a - package_b = target。
        设nums的元素和为sum, 可以列出方程：
        package_a - package_b = target;
        package_a + package_b = sum;
        则 package_a = (target + sum)/2。
        所以根据题意给的target和sum，我们可以求出package_a的值。
        那这道题就可以转化为：给定一个大小为package_a的背包，
        * 有多少种组合方式能把背包装满？ 妥妥的0-1背包。
    * */
	public int findTargetSumWays3(int[] nums, int target) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		int diff = sum - target;
		//sum-target一定是非负偶数，  减去的部分diff, 负数一半正数一半
		//neg=(sum-target)/2
		if (diff < 0 || diff % 2 != 0) {
			return 0;
		}
		int n = nums.length, neg = diff / 2;
		//前i个数选元素等于j的方案，则最终答案为dp[n][neg]
		int[][] dp = new int[n + 1][neg + 1];
		//没有可选的时候边界是1，即选0个和为0一种方案
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			int num = nums[i - 1];
			for (int j = 0; j <= neg; j++) {
				// 先初始长度为i的
				dp[i][j] = dp[i - 1][j];
				if (j >= num) {
					dp[i][j] += dp[i - 1][j - num];
				}
			}
		}
		return dp[n][neg];
	}
	public int findTargetSumWays(int[] nums, int target) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		int diff = sum + target;
		//sum-target一定是非负偶数，  减去的部分diff, 负数一半正数一半
		//neg=(sum-target)/2
		if (diff < 0 || diff % 2 != 0) {
			return 0;
		}
		int n = nums.length, pos = diff / 2;
		//前i个数选元素等于j的方案，则最终答案为dp[n][neg]
		int[][] dp = new int[n + 1][pos + 1];
		//没有可选的时候边界是1，即选0个和为0一种方案
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			int num = nums[i - 1];
			for (int j = 0; j <= pos; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j >= num) {
					dp[i][j] += dp[i - 1][j - num];
				}
			}
		}
		return dp[n][pos];
	}
	//空间优化
	public int findTargetSumWays2(int[] nums, int target) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		int diff = sum - target;
		if (diff < 0 || diff % 2 != 0) {
			return 0;
		}
		int neg = diff / 2;
		int[] dp = new int[neg + 1];
		dp[0] = 1;
		for (int num : nums) {
			//和分割子集一样，倒序避免覆盖
			for (int j = neg; j >= num; j--) {
				dp[j] += dp[j - num];
			}
		}
		return dp[neg];
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
